#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// greatest subarray sum
template<typename Iter>
int greatest_subarr_sum(Iter begin, Iter end) {
  int max_sum = *begin;
  int cur_sum = 0;

  for (Iter iter = begin; iter != end; ++iter) {
    cur_sum += *iter;
    if (cur_sum > max_sum)
      max_sum = cur_sum;

    if (cur_sum < 0) {
      cur_sum = 0; 
      continue;
    }
  }
  return max_sum;
}


// two number with fix sum
bool two_num_fix_sum(int* arr, size_t len, int sum) {
  int begin = 0; 
  int end = len-1;

  while (begin < end) {
    if (arr[begin] + arr[end] == sum)
      return true;
    if (arr[begin] + arr[end] < sum)
      begin++;
    else 
      end--;
  }
  return false;
}

// odd number before even number
template<typename Iter>
void odd_before_even(Iter begin, Iter end) {
  Iter open = begin;
  Iter curr = begin;

  while (curr != end) {
    if (*curr & 1) {
      iter_swap(open++, curr);
    }
    ++curr;
  }
}

// find the only unique number in array
template<typename Iter>
int find_unique(Iter begin, Iter end) {
  int num = 0;
  for (Iter p = begin; p != end; ++p) {
    num ^= *p;
  }
  return num;
}

// find the two unique numbers in array
template<typename Iter>
void find_two_unique(Iter begin, Iter end, int& first, int& second) {
  int xor = 0;
  for (Iter p = begin; p != end; ++p) {
    xor ^= *p;
  }

  size_t mask = 1;
  while (! (xor & mask)) {
    mask <<= 1;
  }

  vector<int> firstarr;
  vector<int> secondarr;
  for (Iter p = begin; p != end; ++p) {
    if (*p & mask) {
      firstarr.push_back(*p);
    }
    else {
      secondarr.push_back(*p);
    }
  }

  first = find_unique(firstarr.begin(), firstarr.end());
  second = find_unique(secondarr.begin(), secondarr.end());
}

// more than  half elem in arr
size_t partition(int* arr, size_t begin, size_t end);

int find_median(int* arr, size_t len) {
  size_t left = 0;
  size_t right = len-1;

  size_t middle = (len-1)/2;
  while (left < right) {
    size_t pivot = partition(arr, left, right);

    if (middle == pivot) 
      return arr[middle];
    else if (middle < pivot)
      right = pivot - 1;
    else
      left = pivot + 1;
  }

  // left == right 
  return arr[left];
}

size_t partition(int* arr, size_t begin, size_t end) { // inclusive
  if (begin > end) 
    throw "begin > end";

  if (begin == end)
    return begin;

  int pivot = arr[end];
  size_t open = begin; 
  size_t curr = begin; 
  while (curr < end) {
    if (arr[curr] < pivot) {
      swap(arr[open++], arr[curr]);
    }
    curr++;
  }
  swap(arr[open], arr[end]);
  
  return open;
}

// min of rotation array
int min_of_rotation_arr(int* arr, size_t len) {
  size_t left = 0;
  size_t right = len-1;

  while (left + 1 < right) {
    size_t middle = (left + right) / 2;
    if (arr[middle] > arr[left]) 
      left = middle;
    else if (arr[middle] < arr[right])
      right = middle;
    else 
      cout << "shouldn't be here" << endl;
  }

  return arr[right];
}

int main() {
  int arr[] = {1, -2, 3, 10, -4, 7, 2, -5};
  cout << "Test greatest subarray sum: " << greatest_subarr_sum(arr, arr+sizeof(arr)/sizeof(int)) << " == 18" << endl;
  
  int negarr[] = {-10, -2, -1, -5};
  cout << "Test greatest subarray sum: " << greatest_subarr_sum(negarr, negarr+sizeof(negarr)/sizeof(int)) << " == -1" << endl;

  int sortedarr[] = {1,2,4,7,11,15};
  cout << "Test two number with fix sum: " << two_num_fix_sum(sortedarr, sizeof(sortedarr)/sizeof(int), 15) << endl;
  cout << "Test two number with fix sum: " << two_num_fix_sum(sortedarr, sizeof(sortedarr)/sizeof(int), 14) << endl;

  cout << "Test odd before even" << endl;
  odd_before_even(sortedarr, sortedarr+sizeof(sortedarr)/sizeof(int));
  for (int i = 0; i < sizeof(sortedarr)/sizeof(int); i++) {
    cout << sortedarr[i] << " ";
  }
  cout << endl;

  int one_unique[] = {1, 2, 3, 1, 2, 4, 5, 5, 4};
  cout << "Test unique number in arr: " << find_unique(one_unique, one_unique+sizeof(one_unique)/sizeof(int)) << endl;

  int two_unique[] = {1, 2, 3, 1, 2, 4, 5, 5};
  int first, second;
  find_two_unique(two_unique, two_unique+sizeof(two_unique)/sizeof(int), first, second);
  cout << "Test unique number in arr: " << first << " and " << second << endl;

  int morethanhalf[] = {1, 2, 1, 3, 1, 4, 1, 5, 1};
  cout << "Test more than half elem in arr: " << find_median(morethanhalf, sizeof(morethanhalf)/sizeof(int)) << endl;
  
  int rotation[] = {4,5,1,2};
  cout << "Test min of rotation arr: " << min_of_rotation_arr(rotation, sizeof(rotation)/sizeof(int)) << endl;

  return 0;
}
